﻿// 3760. 最大剩余油量.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/3763/

一个国家由 n
 个城市组成，这 n
 个城市由 n−1
 条双向道路连接，呈一个树形结构。

每个城市都设有加油站，在第 i
 个城市可以购买 wi
 升汽油。

汽车在道路上行驶，毫无疑问也会消耗汽油，每条道路的具体耗油量也会给出。

现在，需要制定一条汽车的行进路线，从任意城市 s
 出发，经过一条简单路径，到达任意城市 e
 结束。

注意，行进路线也可以只包含一个城市（也就是哪都没去）。

汽车初始时油箱是空的，但是可以在路线中经过的每个城市购买汽油，包括开始城市和最终城市。

如果在一条行进路线中，汽车沿一条道路从某一城市开往另一城市时，现有油量小于该条道路所需油量，那么就说明这条行进路线行不通。

请问，在保证行进路线合理的情况下，汽车在抵达最终城市后，可以剩余的最大油量是多少？

再次提醒，汽车在最终城市也可以加油。

输入格式
第一行包含整数 n
。

第二行包含 n
 个整数 w1,w2,…,wn
。

接下来 n−1
 行，每行包含三个整数 u,v,c
，表示城市 u
 和城市 v
 之间存在一条双向道路，耗油量为 c
。

输出格式
一个整数，表示可能的最大剩余油量。

数据范围
前三个测试点满足，1≤n≤5
。
所有测试点满足，1≤n≤3×105
，0≤wi≤109
，1≤u,v≤n
，1≤c≤109
，u≠v
。

输入样例1：
3
1 3 3
1 2 2
1 3 2
输出样例1：
3
输入样例2：
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
输出样例2：
7
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 